package 贪心.hard;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Lw中
 * @date 2021/9/8 23:15
 */
public class WuLingEr {

    // 502.IPO

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int curr = 0;
        int[][] arr = new int[n][2];

        // 将每个项目的启动资金和对应利润作为子数组存入二维数组中
        for (int i = 0; i < n; ++i) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }

        // 按照二维数组arr中的每一组值的第一个值(启动资金)来从小到大排序：为了让所有启动资金小于等于自身资产的项目都可以加入最大堆中，从而获得正确的最大利润的项目
//        Arrays.sort(arr, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] t1, int[] t2) {
//                return t1[0] - t2[0]; // 如果返回值大于零升序，反之降序
//            }
//        });
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

//        PriorityQueue<Integer> pq1 = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer t1, Integer t2) {
//                return t2 - t1; //强行实现Comparable接口的对象的集合的自然顺序相反：最大堆（默认为最小堆）
//            }
//        });
        // 创建最大堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

        // 最多选择k个不同项目
        for (int i = 0; i < k; ++i) {
            // 在当前项目实行次数小于总项目数与项目启动资本小于等于自身资产前提下，将每一个项目的利润加入最大堆中
            while (curr < n && arr[curr][0] <= w) {
                pq.add(arr[curr][1]);
                curr++;
            }
            if (!pq.isEmpty()) {
                // 将每一轮中最大利润项目的利润值进行累加从而得到最终最大化的利润
                w += pq.poll();
            } else {
                // 当自身资产不足以投资剩余项目时跳出循环
                break;
            }
        }

        return w;
    }

}
